PC World 2000 February/PCWorld_2000-02_cd.bin/Software/Servis/FFE/MISC.SWG/0001_TIFF-BMP-LZW ALGORITHMS.pas

Pascal/Delphi Source File | 1996-09-04 | 34KB | 679 lines

--------!-ALGORITHMS------------------------
Some algorithms used for encoding images etc...
--- TIFF PackBits algorithm

          Abstract

This  document describes a simple compression scheme for bilevel scanned
and paint type files.


          Motivation

The   TIFF  specification  defines  a  number  of  compression  schemes.
Compression  type  1  is really no  compression,  other than basic pixel
packing. Compression type 2, based on CCITT 1D compression, is powerful,
but  not  trivial  to implement. Compression  type  5  is typically very
effective for most bilevel images, as well as many deeper images such as
palette  color  and  grayscale  images,  but  is  also  not  trivial  to
implement. PackBits is a simple but often effective alternative.


          Description

Several  good  schemes  were  already in  use  in  various  settings. We
somewhat  arbitrarily  picked the Macintosh  PackBits scheme. It is byte
oriented,  so there is no problem with word alignment. And it has a good
worst  case  behavior (at most 1 extra  byte for every 128 input bytes).
For Macintosh users, there are toolbox utilities PackBits and UnPackBits
that  will  do  the work for you, but  it  is easy to implement your own
routines.

          A pseudo code fragment to unpack might look like this:

       Loop  until  you  get  the  number  of  unpacked  bytes  you  are
       expecting:
             Read the next source byte into n.
             If n is between 0 and 127 inclusive, copy the next n+1 bytes
          literally.
             Else if  n is  between -127  and -1 inclusive, copy the next
          byte -n+1 times.
             Else if n is 128, noop.
          Endloop

In  the  inverse routine, it's best to  encode  a 2-byte repeat run as a
replicate  run  except when preceded and  followed  by a literal run, in
which  case  it's best to merge the  three  into one literal run. Always
encode 3-byte repeats as replicate runs.

          So that's the algorithm. Here are some other rules:

         o    Each row  must be packed separately.  Do not compress across
              row boundaries.

         o    The number  of uncompressed  bytes per  row is defined to be
         (ImageWidth +  7) / 8.  If the uncompressed bitmap is required to
         have an  even number  of bytes  per row,  decompress  into  word-
         aligned buffers.
         o    If a  run is  larger  than  128  bytes,  simply  encode  the
         remainder of the run as one or more additional replicate runs.

When  PackBits data is uncompressed, the result should be interpreted as
per compression type 1 (no compression).

--- TIFF LZW Compression

          Abstract

This  document  describes  an  adaptive  compression  scheme  for raster
images.

          Reference

Terry  A.  Welch, "A Technique  for  High Performance Data Compression",
IEEE Computer, vol. 17 no. 6 (June 1984). Describes the basic Lempel-Ziv
& Welch (LZW) algorithm. The author's goal in the article is to describe
a  hardware-based compressor that could be  built into a disk controller
or  database engine, and used on all types of data. There is no specific
discussion of raster images. We intend to give sufficient information in
this Appendix so that the article is not required reading.

          Requirements

A compression scheme with the following characteristics should work well
in a desktop publishing environment:

          o    Must work well for images of any bit depth, including images
          deeper than 8 bits per sample.
          o    Must be effective:  an average compression ratio of at least
          2:1 or  better.    And  it  must  have  a  reasonable  worst-case
          behavior, in case something really strange is thrown at it.
          o    Should  not  depend  on  small  variations  between  pixels.
          Palette color  images tend  to contain  abrupt changes  in  index
          values, due to common patterning and dithering techniques.  These
          abrupt changes  do tend to be repetitive, however, and the scheme
          should make use of this fact.
          o    For images  generated by  paint programs,  the scheme should
          not depend on a particular pattern width.  8x8 pixel patterns are
          common now, but we should not assume that this situation will not
          change.
          o    Must be  fast.   It should  not take  more than 5 seconds to
          decompress a  100K byte  grayscale image on a 68020- or 386-based
          computer.   Compression can  be slower,  but probably not by more
          than a factor of 2 or 3.
          o    The level  of implementation  complexity must be reasonable.
          We would like something that can be implemented in no more than a
          couple of  weeks  by  a competent  software  engineer  with  some
          experience  in   image  processing.     The   compiled  code  for
          compression and  decompression combined  should be  no more  than
          about 10K.
          o    Does not require floating point software or hardware.


          The following  sections describe  an algorithm based on the "LZW"
          (Lempel-Ziv & Welch) technique that meets the above requirements.
          In addition  meeting our  requirements,  LZW  has  the  following
          characteristics:

          o    LZW is fully reversible.  All information is preserved.  But
          if noise  or information  is removed  from an  image, perhaps  by
          smoothing or  zeroing some  low-order bitplanes,  LZW  compresses
          images to  a smaller  size.   Thus,   5-bit, 6-bit, or 7-bit data
          masquerading as  8-bit data  compresses better  than  true  8-bit
          data. Smooth  images also  compress better than noisy images, and
          simple images compress better than complex images.
          o    On a  68082- or  386-based computer,  LZW  software  can  be
          written to  compress at  between 30K  and 80K  bytes per  second,
          depending on image characteristics.  LZW decompression speeds are
          typically about 50K bytes per second.
          o    LZW works  well on  bilevel images,  too.   It always  beats
          PackBits,  and   generally  ties   CCITT  1D  (Modified  Huffman)
          compression, on our test images.  Tying CCITT 1D is impressive in
          that LZW  seems to be considerably faster than CCITT 1D, at least
          in our implementation.
          o    Our implementation is written in C, and compiles to about 2K
          bytes of object code each for the compressor and decompressor.
          o    One of  the nice  things about  LZW is that it is used quite
          widely in  other applications  such as  archival programs, and is
          therefore more of a known quantity.


          The Algorithm

Each  strip  is  compressed independently.  We  strongly  recommend that
RowsPerStrip  be  chosen  such that each  strip  contains about 8K bytes
before  compression. We want to keep the strips small enough so that the
compressed  and uncompressed versions of the  strip can be kept entirely
in  memory  even on small machines,  but large enough to maintain nearly
optimal compression ratios.

The LZW algorithm is based on a translation table, or string table, that
maps  strings  of input characters  into  codes. The TIFF implementation
uses  variable-length codes, with a maximum code length of 12 bits. This
string  table  is different for every  strip,  and, remarkably, does not
need  to  be kept around for the  decompressor. The trick is to make the
decompressor  automatically  build  the  same  table  as  is  built when
compressing  the data. We use a C-like pseudocode to describe the coding
scheme:

               InitializeStringTable();
               WriteCode(ClearCode);
               Omega = the empty string;
               for each character in the strip {
                    K = GetNextCharacter();
                    if Omega+K is in the string table {
                         Omega = Omega+K;  /* string concatenation */
                    } else {
                         WriteCode (CodeFromString(Omega));
                         AddTableEntry(Omega+K);
                         Omega = K;
                    }
               } /* end of for loop */
               WriteCode (CodeFromString(Omega));
               WriteCode (EndOfInformation);

That's  it.  The scheme is simple,  although it is fairly challenging to
implement efficiently. But we need a few explanations before we go on to
decompression.

The  "characters" that make up the LZW strings are bytes containing TIFF
uncompressed  (Compression=1)  image  data,  in  our implementation. For
example,  if  BitsPerSample is 4, each  8-bit LZW character will contain
two  4-bit  pixels. If BitsPerSample is  16, each 16-bit pixel will span
two 8-bit LZW characters.

(It  is  also  possible  to implement a  version  of  LZW  where the LZW
character  depth  equals BitsPerSample, as was  described  by Draft 2 of
Revision  5.0.  But  there  is a  major  problem  with this approach. If
BitsPerSample  is greater than 11, we  can not use 12-bit-maximum codes,
so  that the resulting LZW table is unacceptably large. Fortunately, due
to  the adaptive nature of LZW, we  do not pay a significant compression
ratio  penalty  for  combining  several  pixels  into  one  byte  before
compressing.  For  example, our 4-bit  sample  images compressed about 3
percent  worse, and our 1-bit images  compressed about 5 percent better.
And  it  is easier to write an  LZW compressor that always uses the same
character  depth  than  it  is to  write  one  which  can handle varying
depths.)

We  can now describe some of the  routine and variable references in our
pseudocode:

InitializeStringTable()  initializes  the  string  table  to contain all
possible  single-character  strings. There are  256  of them, numbered 0
through 255, since our characters are bytes.

WriteCode()  writes a code to the  output stream. The first code written
is a Clear code, which is defined to be code #256.

          Omega is our "prefix string."

GetNextCharacter()  retrieves  the next character  value  from the input
stream.  This will be number between 0 and 255, since our characters are
bytes.

          The "+" signs indicate string concatenation.

AddTableEntry() adds a table entry. (InitializeStringTable() has already
put  256 entries in our table. Each entry consists of a single-character
string,  and  its associated code value,  which  is, in our application,
identical  to the character itself. That is,  the 0th entry in our table
consists  of  the string <0>, with  corresponding code value of <0>, the
1st  entry  in the table consists  of the string <1>, with corresponding
code value of <1>, ..., and the 255th entry in our table consists of the
string  <255>,  with  corresponding code value  of  <255>.) So the first
entry  that  we add to our string  table will be at position 256, right?
Well,  not quite, since we will reserve  code #256 for a special "Clear"
code,  and code #257 for a  special "EndOfInformation" code that we will
write out at the end of the strip. So the first multiple-character entry
added to the string table will be at position 258.

Let's try an example. Suppose we have input data that looks like:

          Pixel 0:  <7>
          Pixel 1:  <7>
          Pixel 2:  <7>
          Pixel 3:  <8>
          Pixel 4:  <8>
          Pixel 5:  <7>
          Pixel 6:  <7>
          Pixel 7:  <6>
          Pixel 8:  <6>

First, we read Pixel 0 into K. OmegaK is then simply <7>, since Omega is
the  empty string at this point. Is the string <7> already in the string
table?  Of  course, since all single  character  strings were put in the
table  by InitializeStringTable(). So set Omega  equal to <7>, and go to
the top of the loop.

Read Pixel 1 into K. Does OmegaK (<7><7>) exist in the string table? No,
so  we get to do some real work. We write the code associated with Omega
to output (write <7> to output), and add OmegaK (<7><7>) to the table as
entry  258.  Store K (<7>) into Omega.  Note that although we have added
the  string consisting of Pixel 0 and  Pixel 1 to the table, we "re-use"
Pixel 1 as the beginning of the next string.

Back  at  the  top  of the loop. We  read  Pixel  2  into K. Does OmegaK
(<7><7>)  exist in the string table? Yes, the entry we just added, entry
258, contains exactly <7><7>. So we just add K onto the end of Omega, so
that Omega is now <7><7>.

Back  at  the  top  of the loop. We  read  Pixel  3  into K. Does OmegaK
(<7><7><8>)  exist in the string table? No, so write the code associated
with  Omega (<258>) to output, and add OmegaK to the table as entry 259.
Store K (<8>) into Omega.

Back  at  the  top  of the loop. We  read  Pixel  4  into K. Does OmegaK
(<8><8>)  exist  in the string table?  No,  so write the code associated
with  Omega  (<8>) to output, and add  OmegaK to the table as entry 260.
Store K (<8>) into Omega.

          Continuing, we get the following results:

               After reading: We write to output: And add table entry:
               Pixel 0
               Pixel 1   <7>  258: <7><7>
               Pixel 2
               Pixel 3   <258>     259: <7><7><8>
               Pixel 4   <8>  260: <8><8>
               Pixel 5   <8>  261: <8><7>
               Pixel 6
               Pixel 7   <258>     262: <7><7><6>
               Pixel 8   <6>  263: <6><6>

WriteCode()  also  requires  some explanation.  The  output code stream,
<7><258><8><8><258><6>... in our example, should be written using as few
bits as possible. When we are just starting out, we can use 9-bit codes,
since  our  new string table entries are  greater than 255 but less than
512.  But  when we add table entry  512, we must switch to 10-bit codes.
Likewise,  we switch to 11-bit codes at  1024, and 12-bit codes at 2048.
We  will  somewhat arbitrarily limit ourselves  to 12-bit codes, so that
our  table  can  have at most 4096  entries.  If we push it any farther,
tables tend to get too large.

What  happens  if we run out of room  in our string table? This is where
the  afore-mentioned Clear code comes in. As  soon as we use entry 4094,
we write out a (12-bit) Clear code. (If we wait any dworder to write the
Clear  code, the decompressor might try to interpret the Clear code as a
13-bit  code.)  At this point,  the compressor re-initializes the string
table and starts writing out 9-bit codes again.

Note  that whenever you write a code and add a table entry, Omega is not
left empty. It contains exactly one character. Be careful not to lose it
when  you write an end-of-table Clear code.  You can either write it out
as  a 12-bit code before writing the  Clear code, in which case you will
want  to  do it right after adding  table entry 4093, or after the clear
code  as  a  9-bit code. Decompression  gives  the same result in either
case.

To  make  things a little simpler  for the decompressor, we will require
that   each   strip  begins  with  a   Clear  code,  and  ends  with  an
EndOfInformation code.

Every  LZW-compressed  strip must begin on  a byte boundary. It need not
begin on a word boundary. LZW compression codes are stored into bytes in
high-to-low-order  fashion,  i.e.,  FillOrder is  assumed  to  be 1. The
compressed codes are written as bytes, not words, so that the compressed
data will be identical regardless of whether it is an "II" or "MM" file.

Note  that the LZW string table is a continuously updated history of the
strings  that  have been encountered in  the  data. It thus reflects the
characteristics of the data, providing a high degree of adaptability.


          LZW Decoding

          The procedure for decompression is a little more complicated, but
          still not too bad:

               while ((Code = GetNextCode()) != EoiCode) {
                    if (Code == ClearCode) {
                         InitializeTable();
                         Code = GetNextCode();
                         if (Code == EoiCode)
                              break;
                         WriteString(StringFromCode(Code));
                         OldCode = Code;
                    }  /* end of ClearCode case */

                    else {
                         if (IsInTable(Code)) {
                              WriteString(StringFromCode(Code));
                              AddStringToTable(StringFromCode(OldCode)+
                                FirstChar(StringFromCode(Code)));
                              OldCode = Code;
                         } else {
                              OutString = StringFromCode(OldCode) +
                                  FirstChar(StringFromCode(OldCode));
                              WriteString(OutString);
                              AddStringToTable(OutString);
                              OldCode = Code;
                         }
                    } /* end of not-ClearCode case */
               } /* end of while loop */

The  function GetNextCode() retrieves the next  code from the LZW- coded
data. It must keep track of bit boundaries. It knows that the first code
that it gets will be a 9-bit code. We add a table entry each time we get
a  code,  so GetNextCode() must switch over  to  10-bit codes as soon as
string #511 is stored into the table.

The   function  StringFromCode()  gets  the  string  associated  with  a
particular code from the string table.

The  function AddStringToTable() adds a string  to the string table. The
"+"  sign  joining  the two parts  of  the  argument to AddStringToTable
indicate string concatenation.

StringFromCode() looks up the string associated with a given code.

          WriteString() adds a string to the output stream.


          When SamplesPerPixel Is Greater Than 1

We  have  so far described the  compression scheme as if SamplesPerPixel
were  always 1, as will be be  the case with palette color and grayscale
images. But what do we do with RGB image data?

Tests  on  our sample images indicate  that the LZW compression ratio is
nearly   identical   regardless  of   whether  PlanarConfiguration=1  or
PlanarConfiguration=2,  for  RGB images.  So use whichever configuration
you prefer, and simply compress the bytes in the strip.

It  is  worth cautioning that compression  ratios on our test RGB images
were  disappointing  low:  somewhere  between 1.1  to  1  and  1.5 to 1,
depending  on the image. Vendors are urged to do what they can to remove
as  much noise from their images as possible. Preliminary tests indicate
that  significantly  better  compression ratios  are  possible with less
noisy  images.  Even  something  as simple  as  zeroing  out  one or two
least-significant  bitplanes  may be quite  effective, with little or no
perceptible image degradation.


          Implementation

The exact structure of the string table and the method used to determine
if  a  string is already in the  table are probably the most significant
design   decisions  in  the  implementation  of  a  LZW  compressor  and
decompressor.  Hashing has been suggested as  a useful technique for the
compressor. We have chosen a tree based approach, with good results. The
decompressor  is actually more straightforward, as well as faster, since
no search is involved - strings can be accessed directly by code value.


          Performance

Many  people  do  not realize that  the  performance  of any compression
scheme  depends  greatly on the type of  data  to which it is applied. A
scheme that works well on one data set may do poorly on the next.

But  since we do not want to  burden the world with too many compression
schemes,  an  adaptive scheme such as LZW  that performs quite well on a
wide  range of images is very desirable. LZW may not always give optimal
compression ratios, but its adaptive nature and relative simplicity seem
to make it a good choice.

Experiments  thus far indicate that we  can expect compression ratios of
between  1.5 and 3.0 to 1 from LZW,  with no loss of data, on continuous
tone  grayscale scanned images. If we  zero the least significant one or
two  bitplanes  of  8-bit  data, higher  ratios  can  be achieved. These
bitplanes  often  consist chiefly of noise,  in  which case little or no
loss in image quality will be perceived. Palette color images created in
a  paint  program  generally compress  much  better than continuous tone
scanned images, since paint images tend to be more repetitive. It is not
unusual  to  achieve compression ratios of 10  to 1 or better when using
LZW on palette color paint images.

By way of comparison, PackBits, used in TIFF for black and white bilevel
images,  does  not do well on  color  paint images, much less continuous
tone grayscale and color images. 1.2 to 1 seemed to be about average for
4-bit images, and 8-bit images are worse.

It  has  been  suggested  that the CCITT  1D  scheme  could  be used for
continuous  tone  images,  by compressing  each  bitplane separately. No
doubt  some compression could be achieved,  but it seems unlikely that a
scheme  based  on  a fixed table that  is  optimized for word black runs
separated  by  dworder white runs would be  a very good choice on any of
the  bitplanes. It would do quite  well on the high-order bitplanes (but
so  would a simpler scheme like PackBits),  and would do quite poorly on
the  low-order  bitplanes. We believe  that the compression ratios would
generally  not be very impressive, and  the process would in addition be
quite  slow.  Splitting the pixels into  bitplanes and putting them back
together  is somewhat expensive, and the coding is also fairly slow when
implemented in software.

Another  approach  that has been suggested  uses  uses a 2D differencing
step  following  by  coding  the  differences  using  a  fixed  table of
variable-length  codes.  This  type of scheme  works  quite well on many
8-bit  grayscale images, and is probably  simpler to implement than LZW.
But  it  has  a number of disadvantages  when  used on a wide variety of
images.  First,  it  is not adaptive.  This  makes a big difference when
compressing  data such as 8-bit images  that have been "sharpened" using
one  of the standard techniques. Such  images tend to get larger instead
of  smaller  when compressed. Another  disadvantage  of these schemes is
that  they do not do well with a  wide range of bit depths. The built-in
code table has to be optimized for a particular bit depth in order to be
effective.

Finally,  we  should  mention  "lossy"  compression  schemes.  Extensive
research   has   been   done   in   the   area   of   lossy,   or   non-
information-preserving  image  compression.  These  techniques generally
yield   much   higher  compression  ratios   than  can  be  achieved  by
fully-reversible,  information-preserving  image  compression techniques
such  as  PackBits  and  LZW.  Some  disadvantages:  many  of  the lossy
techniques  are  so computationally expensive  that hardware assists are
required.  Others  are so complicated  that  most microcomputer software
vendors  could  not afford either the  expense  of implementation or the
increase  in  application object code  size. Yet others sacrifice enough
image quality to make them unsuitable for publishing use.

In  spite of these difficulties, we believe that there will one day be a
standardized lossy compression scheme for full color images that will be
usable  for publishing applications  on microcomputers. An International
Standards  Organization group, ISO/IEC/JTC1/SC2/WG8, in cooperation with
CCITT  Study  Group  VIII,  is hard at  work  on  a scheme that might be
appropriate.  We expect that a future  revision of TIFF will incorporate
this  scheme once it is finalized, if  it turns out to satisfy the needs
of  desktop  publishers and others  in the microcomputer community. This
will  augment, not replace, LZW as  an approved TIFF compression scheme.
LZW  will  very  likely remain the  scheme  of  choice for Palette color
images,  and perhaps 4-bit grayscale images, and may well overtake CCITT
1D and PackBits for bilevel images.


          Future LZW Extensions

Some images compress better using LZW coding if they are first subjected
to  a  process  wherein each pixel  value  is replaced by the difference
between  the pixel and the preceding pixel. Performing this differencing
in  two dimensions helps some images  even more. However, many images do
not compress better with this extra preprocessing, and for a significant
number  of  images,  the  compression ratio  is  actually  worse. We are
therefore  not  making  differencing an integral  part  of  the TIFF LZW
compression scheme.

However,  it is possible that a "prediction" stage like differencing may
exist  which is effective over a broad range of images. If such a scheme
is found, it may be incorporated in the next major TIFF revision. If so,
a new value will be defined for the new "Predictor" TIFF tag. Therefore,
all TIFF readers that read LZW files must pay attention to the Predictor
tag.  If  it  is  1, which is  the  default  case, LZW decompression may
proceed  safely.  If it is not 1,  and the reader does not recognize the
specified prediction scheme, the reader should give up.


          Acknowledgements

The  original LZW reference has already been given. The use of ClearCode
as  a  technique  to handle overflow  was  borrowed from the compression
scheme    used   by   the   Graphics   Interchange   Format   (GIF),   a
small-color-paint-image-file  format used by CompuServe  that also is an
adaptation  of the LZW technique. Joff Morgan and Eric Robinson of Aldus
were each instrumental in their own way in getting LZW off the ground.

          The TIFF predictor algorithm

The  idea  is to make use of  the  fact that many continuous tone images
rarely  vary  much  in pixel value from  one  pixel to the next. In such
images,   if  we  replace  the   pixel  values  by  differences  between
consecutive  pixels, many of the differences  should be 0, plus or minus
1,  and  so on. This reduces  the apparent information content, and thus
allows LZW to encode the data more compactly.

Assuming 8-bit grayscale pixels for the moment, a basic C implementation
might look something like this:

               char image[ ][ ];
               int  row, col;

               /* take horizontal differences:
                */
               for (row = 0; row < nrows; row++)
                    for (col = ncols - 1; col >= 1; col--)
                         image[row][col] -= image[row][col-1];

If we don't have 8-bit samples, we need to work a little harder, so that
we can make better use of the architecture of most CPUs. Suppose we have
4-bit  samples, packed two to a byte, in normal TIFF uncompressed (i.e.,
Compression=1)  fashion. In order to find  differences, we want to first
expand  each 4-bit sample into an 8-bit byte, so that we have one sample
per  byte,  low-order  justified. We  then  perform the above horizontal
differencing.  Once the differencing has  been completed, we then repack
the  4-  bit  differences  two to  a  byte,  in normal TIFF uncompressed
fashion.

If  the samples are greater than 8 bits deep, expanding the samples into
16-bit  words instead of 8-bit bytes seems  like the best way to perform
the subtraction on most computers.

Note  that we have not lost any data  up to this point, nor will we lose
any  data  later on. It might at  first seem that our differencing might
turn  8-bit  samples into 9-bit differences,  4-  bit samples into 5-bit
differences,  and so on. But it turns  out that we can completely ignore
the "overflow" bits caused by subtracting a larger number from a smaller
number  and  still  reverse  the  process  without  error.  Normal  twos
complement  arithmetic does just what we want. Try an example by hand if
you need more convincing.

Up  to  this  point we have  implicitly  assumed that we are compressing
bilevel  or grayscale images. An  additional consideration arises in the
case of color images.

If  PlanarConfiguration is 2, there is no problem. Differencing proceeds
the same way as it would for grayscale data.

If  PlanarConfiguration is 1, however, things  get a little trickier. If
we didnt do anything special, we would be subtracting red sample values
from  green sample values, green sample  values from blue sample values,
and  blue sample values from red sample values, which would not give the
LZW  coding  stage  much  redundancy to work  with.  So  we  will do our
horizontal  differences with an offset of SamplesPerPixel (3, in the RGB
case).  In other words, we will subtract red from red, green from green,
and   blue  from  blue.  The  LZW  coding  stage  is  identical  to  the
SamplesPerPixel=1  case.  We require that  BitsPerSample be the same for
all 3 samples.


          Results and guidelines

LZW  without  differencing works well  for 1-bit images, 4-bit grayscale
images,  and synthetic color images. But natural 24-bit color images and
some  8-bit  grayscale  images  do  much  better  with differencing. For
example,  our 24-bit natural test images  hardly compressed at all using
"plain"  LZW:  the average compression ratio  was 1.04 to 1. The average
compression  ratio  with  horizontal  differencing  was  1.40  to  1. (A
compression  ratio of 1.40 to 1 means  that if the uncompressed image is
1.40MB in size, the compressed version is 1MB in size.)

Although the combination of LZW coding with horizontal differencing does
not  result in any loss of data, it may be worthwhile in some situations
to  give up some information by removing  as much noise as possible from
the  image  data  before doing  the  differencing, especially with 8-bit
samples.  The simplest way to get rid of noise is to mask off one or two
low-  order  bits of each 8-bit sample.  On  our 24-bit test images, LZW
with horizontal differencing yielded an average compression ratio of 1.4
to  1.  When  the  low-order  bit  was  masked  from  each  sample,  the
compression  ratio climbed to 1.8 to 1; the compression ratio was 2.4 to
1  when  masking  two  bits, and 3.4  to  1  when masking three bits. Of
course,  the more you mask, the  more you risk losing useful information
adword  with the noise. We encourage you  to experiment to find the best
compromise  for  your device. For some  applications it may be useful to
let the user make the final decision.

Interestingly,  most of our RGB  images compressed slightly better using
PlanarConfiguration=1.  One might think that compressing the red, green,
and blue difference planes separately (PlanarConfiguration=2) might give
better  compression results than mixing  the differences together before
compressing  (PlanarConfiguration=1), but this does not appear to be the
case.

Incidentally,  we tried taking both horizontal and vertical differences,
but  the extra complexity of two-dimensional differencing did not appear
to  pay  off for most of our test  images. About one third of the images
compressed  slightly better with two-dimensional differencing, about one
third compressed slightly worse, and the rest were about the same.

--- BMP RLE_8 compression

The BMP can be compressed in two modes, absolute mode and RLE mode. Both
modes can occur anywhere in a single bitmap.

The  RLE  mode  is a simple RLE  mechanism,  the first byte contains the
count,  the second byte the pixel to be replicatet. If the count byte is
0, the second byte is a special, like EOL or delta.

In  absolute  mode, the second byte contains  the  number of bytes to be
copied  litteraly. Each absolute run must be word-aligned that means you
will  may have to add an aditional padding byte which is not included in
the count. After an absolute run, RLE compression continues.

          Second byte           Meaning

                 0              End of line
                 1              End of bitmap
                 2              Delta. The next two bytes are the horizontal
                                and vertical offsets from the current position
                                to the next pixel.
             3-255              Switch to absolute mode

--- BMP RLE_4 compression

RLE_4 compression knows the two modes of the RLE_8 compression, absolute
and RLE. In the RLE mode, the first byte contains the count of pixels to
draw,  the  second byte contains in its  two nibbles the indices off the
pixel colors, the higher 4 bits are the left pixel, the lower 4 bits are
the  right  pixel. Note that two-color  runs are possible to encode with
RLE_4 through this.

--- Protracker sample compression / decompression

Get the number of sample bytes to process. Call this SamplesLeft.

          Set Delta counter to 0.

          DO
            Get a byte from the buffer.
            Store the byte in Temp.
            Subtract the Delta counter from the byte.
            Store it in the buffer.
            Move the Temp byte into the Delta Counter
            Decrement SamplesLeft.
          WHILE(SamplesLeft <> 0)

          The technique for conversion back to the raw data is:

          Get the number of sample bytes to process.
          Call this SamplesLeft.

          Set Delta counter to 0.

          DO
            Get a byte from the buffer.
            Add onto the byte the Delta Counter.
            Store the byte in Delta Counter.
            Store the byte in Temp.
            Decrement SamplesLeft.
          WHILE(SamplesLeft <> 0)